翻訳と辞書
Words near each other
・ Worst Fears Confirmed
・ Worst Forms of Child Labour Convention
・ Worst Forms of Child Labour Recommendation
・ Worst Forms of Hazards faced by Children at Work
・ Worst Friends
・ Worst Friends (2009 film)
・ Worst Friends (2014 film)
・ Worst movie ever
・ Worst Part Is Over
・ Worst railway accidents in Australia
・ Worst Superpower Ever
・ Worst Thing I've Been Cursed With
・ Worst Week
・ Worst Year of My Life Again
・ Worst-case circuit analysis
Worst-case complexity
・ Worst-case distance
・ Worst-case execution time
・ Worst-case scenario
・ Worst-Case Scenario (TV series)
・ Worst-Case Scenario series
・ Worst. Person. Ever.
・ Worstead
・ Worstead railway station
・ Worsted
・ Worsted Act 1776
・ Worster-Drought syndrome
・ Worsthorne
・ Worsthorne-with-Hurstwood
・ Worston


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Worst-case complexity : ウィキペディア英語版
Worst-case complexity
In computer science, the worst-case complexity (usually denoted in asymptotic notation) measures the resources (e.g. running time, memory) an algorithm requires in the worst-case. It gives an upper bound on the resources required by the algorithm.
In the case of running time, the worst-case time-complexity indicates the longest running time performed by an algorithm given ''any'' input of size ''n'', and thus this guarantees that the algorithm finishes on time. Moreover, the order of growth of the worst-case complexity is used to compare the efficiency of two algorithms.
The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input.
== Definition ==

:Given a model of computation and an algorithm A that halts on each input ''x'', the mapping ''t''A:
*→N is called the time complexity of A if, for every ''x'', A halts after exactly ''t''A(''x'') steps.
Since we usually are interested in the dependence of the time complexity on different input length, abusing terminology, the time complexity is sometimes referred to the mapping TA:N→N, defined by TA(''n''):= maxx∈n.
Similar definitions can be given for space complexity, randomness complexity, etc.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Worst-case complexity」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.